package problem30;


//30.串联所有单词的子串
//https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int n = s.length(), m = words[0].length();
        HashMap<String, Integer> hash1 = new HashMap<>();
        for(String str : words) {
            hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        }
        List<Integer> list = new ArrayList<>();
        for(int k = 0; k<m; k++) {
            HashMap<String, Integer> hash2 = new HashMap<>();
            int count = 0;
            for(int j = k, i = k; j<=n-m; j+=m) {
                String str = s.substring(j, j+m);
                // System.out.println(str);
                hash2.put(str, hash2.getOrDefault(str, 0) + 1);
                if(hash2.get(str).equals(hash1.getOrDefault(str, 0))) {
                    count++;
                }
                
                if((j-i+1) > words.length*m) {
                    String tmp = s.substring(i, i+m);
                    System.out.println(tmp);
                    if(hash1.getOrDefault(tmp, 0) == hash2.getOrDefault(tmp, 0)) count--;
                    hash2.put(tmp, hash2.get(tmp)-1);
                    i+=m;
                }
                
                if(count == hash1.size()) {
                    list.add(i);
                }
            }
        }
        return list;
    }
}